// 字符串
// 常见题型- 找最长公共前缀 - 统一对比
// 常见题型 - 找回文串 - 用中心扩展算法
// 常见题型- 高精度模拟加减乘除法，需要按照题意进行模拟

// 例题 3：
// 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
//
//        示例 1：
//
//        输入:a = "11", b = "1"
//        输出："100"
//        示例 2：
//
//        输入：a = "1010", b = "1011"
//        输出："10101"
//
//        提示：
//
//        1 <= a.length, b.length <= 104
//        a 和 b 仅由字符 '0' 或 '1' 组成
//        字符串如果不是 "0" ，就不含前导零

// 解题思路：
// 模拟二进制加法
// 虽然题目给的是字符串，但是我们还是需要把字符转化成数字
// 注意需要从 字符串最后面的位置 开始加，加法的最低位在最右边

public class AddBinary {
    public String addBinary(String a, String b) {
        int len1 = a.length();
        int len2 = b.length();
        char[] aa = a.toCharArray();
        char[] bb = b.toCharArray();
        int i = 0;
        int t = 0;
        StringBuilder ret = new StringBuilder();
        while(i < len1 || i < len2 || t != 0){
            if(i < len1) t += aa[len1 - 1 - i] - '0';
            if(i < len2) t += bb[len2 - 1 - i] - '0';
            ret.append(t % 2);
            t /= 2;
            i++;
        }
        return ret.reverse().toString();
    }
}
